#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:

    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n; int rem_color;

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if (color == image[sr][sc])
            return image;
        m = image.size();
        n = image[0].size();
        rem_color = image[sr][sc];
        image[sr][sc] = color;
        dfs(image, sr, sc, color);
        return image;
    }

    void dfs(vector<vector<int>>& image, int x, int y, int color)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && image[xx][yy] == rem_color) {
                image[xx][yy] = color;
                dfs(image, xx, yy, color);
            }
        }
    }
};

class Solution {
public:

    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    grid[i][j] = '0';
                    dfsss(grid, i, j);
                    // for(int a = 0;a < m;a++){
                    //     for(int b = 0;b < n;b++){
                    //         cout << grid[a][b] << " ";
                    //     }
                    //     cout << endl;
                    // }
                    // cout << endl;
                }

            }
        }
        return ans;
    }

    void dfsss(vector<vector<char>>& grid, int x, int y)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == '1') {
                grid[xx][yy] = '0';
                dfsss(grid, xx, yy);
            }
        }
    }

};

class Solution {
public:

    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    int m, n;
    bool vis[55][55];
    int ans, tmpans;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    vis[i][j] = true;
                    tmpans++;
                    dfs(grid, i, j);
                    ans = max(ans, tmpans);
                    tmpans = 0;
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>>& grid, int x, int y)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy] && grid[xx][yy] == 1) {
                vis[xx][yy] = true;
                tmpans++;
                dfs(grid, xx, yy);
            }
        }
    }

};

class Solution {
public:

    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[210][210];
    int m, n;

    void solve(vector<vector<char>>& board) {
        n = board.size();
        m = board[0].size();
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O' && !vis[i][0])
                vis[i][0] = true, dfs(board, i, 0);
            if (board[i][m - 1] == 'O' && !vis[i][m - 1])
                vis[i][m - 1] = true, dfs(board, i, m - 1);
        }
        for (int j = 1; j < m - 1; j++) {
            if (board[0][j] == 'O' && !vis[0][j])
                vis[0][j] = true, dfs(board, 0, j);
            if (board[n - 1][j] == 'O' && !vis[n - 1][j])
                vis[n - 1][j] = true, dfs(board, n - 1, j);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && !vis[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    void dfs(vector<vector<char>>& board, int x, int y)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && board[xx][yy] == 'O') {
                vis[xx][yy] = true;
                dfs(board, xx, yy);
            }
        }
    }
};

class Solution {
public:

    bool vis1[210][210];
    bool vis2[210][210];
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size();
        n = heights[0].size();
        for (int i = 0; i < n; i++) {
            if (!vis1[0][i]) {
                vis1[0][i] = true;
                dfs1(heights, 0, i);
            }
        }
        for (int i = 0; i < m; i++) {
            if (!vis1[i][0]) {
                vis1[i][0] = true;
                dfs1(heights, i, 0);
            }
        }
        for (int i = 0; i < n; i++) {
            if (!vis2[m - 1][i]) {
                vis2[m - 1][i] = true;
                dfs2(heights, m - 1, i);
            }
        }
        for (int i = 0; i < m; i++) {
            if (!vis2[i][n - 1]) {
                vis2[i][n - 1] = true;
                dfs2(heights, i, n - 1);
            }
        }

        vector<vector<int>> ans;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis1[i][j] && vis2[i][j]) {
                    ans.push_back({ i, j });
                }
            }
        }
        return ans;
    }

    void dfs1(vector<vector<int>>& heights, int x, int y)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis1[xx][yy] && heights[xx][yy] >= heights[x][y]) {
                vis1[xx][yy] = true;
                dfs1(heights, xx, yy);
            }
        }
    }

    void dfs2(vector<vector<int>>& heights, int x, int y)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis2[xx][yy] && heights[xx][yy] >= heights[x][y]) {
                vis2[xx][yy] = true;
                dfs2(heights, xx, yy);
            }
        }
    }
};

class Solution {
public:

    int m, n;
    vector<vector<char>> gameMap;
    int dx[8] = { 1,-1,0,0,1,-1,1,-1 };
    int dy[8] = { 0,0,1,-1,1,1,-1,-1 };

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size();
        n = board[0].size();
        gameMap.resize(m, vector<char>(n, '0'));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'M') {
                    gameMap[i][j] = 'X';
                    for (int k = 0; k < 8; k++) {
                        int xx = i + dx[k];
                        int yy = j + dy[k];
                        if (xx >= 0 && xx < m && yy >= 0 && yy < n)
                            gameMap[xx][yy] += 1;
                    }
                }
            }
        }

        // for(int i = 0;i < m;i++){
        //     for(int j = 0;j < n;j++){
        //         cout << gameMap[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        // return {};

        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        else if (gameMap[x][y] != '0') {
            board[x][y] = gameMap[x][y];
            return board;
        }
        else {
            board[x][y] = 'B';
            dfs(board, x, y);
            return board;
        }
    }

    void dfs(vector<vector<char>>& board, int x, int y)
    {
        for (int k = 0; k < 8; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'E') {
                if (gameMap[xx][yy] == '0') {
                    board[xx][yy] = 'B';
                    dfs(board, xx, yy);
                }
                else if (gameMap[xx][yy] > '0' && gameMap[xx][yy] < '9') {
                    board[xx][yy] = gameMap[xx][yy];
                }
            }
        }
    }

};

class Solution {
public:
    int dx[2] = { 1,0 };
    int dy[2] = { 0,1 };
    int ans;
    int mm, nn, cntt;
    bool vis[110][110];

    int wardrobeFinishing(int m, int n, int cnt) {
        mm = m;
        nn = n;
        cntt = cnt;
        ans++;
        vis[0][0] = true;
        dfs(0, 0);
        return ans;
    }

    void dfs(int x, int y)
    {
        for (int k = 0; k < 2; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx < 0 || xx >= mm || yy < 0 || yy >= nn)
                continue;
            if (deal_digit(xx) + deal_digit(yy) > cntt)
                continue;
            if (!vis[xx][yy]) {
                vis[xx][yy] = true;
                ans++;
                dfs(xx, yy);
            }
        }
    }

    int deal_digit(int d)
    {
        int tmp = 0;
        while (d > 0) {
            tmp += d % 10;
            d /= 10;
        }
        return tmp;
    }

};

